package com.LeetCode.Learning;

import java.util.Arrays;
import java.util.Scanner;

/**942. 增减字符串匹配
 简单
 由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'
 给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。



 示例 1：

 输入：s = "IDID"
 输出：[0,4,1,3,2]
 示例 2：

 输入：s = "III"
 输出：[0,1,2,3]-
 示例 3：

 输入：s = "DDI"
 输出：[3,2,0,1]


 提示：

 1 <= s.length <= 105
 s 只包含字符 "I" 或 "D"

 考虑 perm[0]\textit{perm}[0]perm[0] 的值，根据题意：

 如果 s[0]=‘I’s[0]=\texttt{`I'}s[0]=‘I’，那么令 perm[0]=0\textit{perm}[0]=0perm[0]=0，
 则无论 perm[1]\textit{perm}[1]perm[1] 为何值都满足 perm[0]<perm[1]\textit{perm}[0] < \textit{perm}[1]perm[0]<perm[1]；
 如果 s[0]=‘D’s[0]=\texttt{`D'}s[0]=‘D’，那么令 perm[0]=n\textit{perm}[0]=nperm[0]=n，
 则无论 perm[1]\textit{perm}[1]perm[1] 为何值都满足 perm[0]>perm[1]\textit{perm}[0] > \textit{perm}[1]perm[0]>perm[1]；
 确定好 perm[0]\textit{perm}[0]perm[0] 后，剩余的 n−1n-1n−1 个字符和 nnn 个待确定的数就变成了一个和原问题相同，但规模为 n−1n-1n−1 的问题。因此我们可以继续按照上述方法确定 perm[1]\textit{perm}[1]perm[1]：如果 s[1]=‘I’s[1]=\texttt{`I'}s[1]=‘I’，那么令 perm[1]\textit{perm}[1]perm[1] 为剩余数字中的最小数；如果 s[1]=‘D’s[1]=\texttt{`D'}s[1]=‘D’，那么令 perm[1]\textit{perm}[1]perm[1] 为剩余数字中的最大数。如此循环直至剩下一个数，填入 perm[n]\textit{perm}[n]perm[n] 中。

 代码实现时，由于每次都选择的是最小数和最大数，我们可以用两个变量 lo\textit{lo}lo 和 hi\textit{hi}hi 表示当前剩余数字中的最小数和最大数。

 作者：力扣官方题解
 链接：https://leetcode.cn/problems/di-string-match/solutions/1473721/zeng-jian-zi-fu-chuan-pi-pei-by-leetcode-jzm2/
 来源：力扣（LeetCode）
 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */

public class IncreaseDecreaseStringMatching {
    public static void main(String[] args) {
        IncreaseDecreaseStringMatching solution = new IncreaseDecreaseStringMatching();

        // 测试1
        String s1 = "IDID";
        int[] result1 = solution.diStringMatch(s1);
        System.out.println(Arrays.toString(result1)); // 输出: [0, 4, 1, 3, 2]

        // 测试2
        String s2 = "III";
        int[] result2 = solution.diStringMatch(s2);
        System.out.println(Arrays.toString(result2)); // 输出: [0, 1, 2, 3]

        // 测试3
        String s3 = "DDI";
        int[] result3 = solution.diStringMatch(s3);
        System.out.println(Arrays.toString(result3)); // 输出: [3, 2, 0, 1]
    }
    public int[] diStringMatch(String s) {
        int n = s.length(), lo = 0, hi = n;
        int[] perm = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            perm[i] = s.charAt(i) == 'I' ? lo++ : hi--;
        }
        perm[n] = lo; // 最后剩下一个数，此时 lo == hi
        return perm;
    }
}
